package com.sheng.leetcode.year2022.swordfingeroffer.day11;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2022/09/09
 *<p>
 * 剑指 Offer 22. 链表中倒数第k个节点<p>
 *<p>
 * 输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。<p>
 * 例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。<p>
 *<p>
 * 示例：<p>
 *<p>
 * 给定一个链表: 1->2->3->4->5, 和 k = 2.<p>
 *<p>
 * 返回链表 4->5.<p>
 *<p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof">...</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class Sword0022 {

    @Test
    public void test01() {
        ListNode head = new ListNode(1);
        ListNode listNode5 = new ListNode(6);
        ListNode listNode4 = new ListNode(5);
        ListNode listNode3 = new ListNode(4);
        ListNode listNode2 = new ListNode(3);
        ListNode listNode1 = new ListNode(2);
        listNode4.next = listNode5;
        listNode3.next = listNode4;
        listNode2.next = listNode3;
        listNode1.next = listNode2;
        head.next = listNode1;
        int k = 2;
        System.out.println(new Solution22().getKthFromEnd(head, k));
    }
}
//class Solution22 {
//    public ListNode getKthFromEnd(ListNode head, int k) {
//        if (head == null) {
//            return null;
//        }
//        int size = 1;
//        ListNode pre = head;
//        ListNode cur = head.next;
//        while (cur != null) {
//            size++;
//            pre = cur;
//            cur = pre.next;
//        }
//        ListNode node = head;
//        int x = size - k + 1;
//        while (x > 1) {
//            node = node.next;
//            x--;
//        }
//        return node;
//    }
//}
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */

class Solution22 {
    public ListNode getKthFromEnd(ListNode head, int k) {
        // 用作后面计数
        ListNode former = head, latter = head;
        for(int i = 0; i < k; i++) {
            former = former.next;
        }
        while(former != null) {
            former = former.next;
            latter = latter.next;
        }
        return latter;
    }
}
//
//作者：jyd
//链接：https://leetcode.cn/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/solution/mian-shi-ti-22-lian-biao-zhong-dao-shu-di-kge-j-11/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
